//
// Created by yangchao on 2022/4/25.
// 19. 删除链表的倒数第 N 个结点: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
//
#include "../DataStructure/ListNode.h"

class RemoveNthFromEnd {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* node = head;
        int len = 0;
        while (node != nullptr) {
            len++;
            node = node->next;
        }
        if (len == 0) return nullptr;
        n = n % len;
        if (n == 0) return head->next;
        int k = len - n;
        ListNode* pNode = head;
        for (int i = 0; i < k-1; ++i) {
            pNode = pNode->next;
        }
        pNode->next = pNode->next->next;
        return head;
    }

    //方法2：双指针
    ListNode* removeNthFromEnd2(ListNode* head, int n) {
        ListNode* dummy = new ListNode(-1,head);
        ListNode* pre = dummy;
        ListNode* pt = head;
        for (int i = 0; i < n; i++) {
            pt = pt->next;
        }
        while (pt != nullptr) {
            pre = pre->next;
            pt = pt->next;
        }
        pre->next = pre->next->next;
        return dummy->next;


    }
};
